import java.util.*;

//课程表 II
//测试链接：https://leetcode.cn/problems/course-schedule-ii/
public class FindOrder {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        Map<Integer, List<Integer>> edges = new HashMap<>();

        for(int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][0], b = prerequisites[i][1]; //b->a
            if(!edges.containsKey(b)) {
                edges.put(b,new ArrayList<>());
            }
            edges.get(b).add(a);
            in[a]++;
        }

        int[] ans = new int[numCourses];
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < numCourses; i++) {
            if(in[i] == 0) q.add(i);
        }

        int index = 0;
        while(!q.isEmpty()) {
            int m = q.poll();
            ans[index++] = m;

            for(int n : edges.getOrDefault(m,new ArrayList<>())) {
                in[n]--;
                if(in[n] == 0) q.add(n);
            }
        }

        for(int i = 0; i < numCourses; i++) {
            if(in[i] != 0) return new int[]{};
        }
        return ans;
    }
}
